{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove K Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeKdigits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移掉 K 位数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个以字符串表示的非负整数 <code>num</code> 和一个整数 <code>k</code> ，移除这个数中的 <code>k</code><em> </em>位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。</p>\n",
    " \n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"1432219\", k = 3\n",
    "<strong>输出：</strong>\"1219\"\n",
    "<strong>解释：</strong>移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"10200\", k = 1\n",
    "<strong>输出：</strong>\"200\"\n",
    "<strong>解释：</strong>移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"10\", k = 2\n",
    "<strong>输出：</strong>\"0\"\n",
    "<strong>解释：</strong>从原数字移除所有的数字，剩余为空就是 0 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= k <= num.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>num</code> 仅由若干位数字（0 - 9）组成</li>\n",
    "\t<li>除了 <strong>0</strong> 本身之外，<code>num</code> 不含任何前导零</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-k-digits](https://leetcode.cn/problems/remove-k-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-k-digits](https://leetcode.cn/problems/remove-k-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1432219\"\\n3', '\"10200\"\\n1', '\"10\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        elif k>10000:\n",
    "            a=min(num)\n",
    "            b=num.count(a)\n",
    "            c=a * min(b,len(num)-k)\n",
    "            # if b<len(num)-k:\n",
    "            #     for i in range(min(b,len(num)-k)):\n",
    "            #         c.append(a + \"1\")\n",
    "            return c\n",
    "        num=list(num)\n",
    "        \n",
    "        for i in range(k):\n",
    "            j = 0\n",
    "            while j < len(num) - 1 and num[j] <= num[j + 1] :\n",
    "                j+=1\n",
    "            num.remove(num[j])\n",
    "        num=\"\".join(num)\n",
    "        num=num.lstrip(\"0\")\n",
    "        return \"0\" if num == \"\" else num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num)<=k:return \"0\"\n",
    "        l=0\n",
    "        while k>0 and l<len(num)-1:\n",
    "            if num[l]>num[l+1]:\n",
    "                num=num[0:l]+num[l+1:]\n",
    "                if l>0:\n",
    "\n",
    "                    l-=1\n",
    "                k-=1\n",
    "            else:l+=1\n",
    "\n",
    "\n",
    "        if l==len(num)-1:\n",
    "            while k>0:\n",
    "                num=num[:-1]\n",
    "                k-=1\n",
    "\n",
    "        while len(num)>=1 and num[0]=='0':\n",
    "\n",
    "\n",
    "\n",
    "            num=num[1:]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        return num if num!=\"\" else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num)<=k:return \"0\"\n",
    "        l=0\n",
    "        while k>0 and l<len(num)-1:\n",
    "            if num[l]>num[l+1]:\n",
    "                num=num[0:l]+num[l+1:]\n",
    "                if l>0:\n",
    "\n",
    "                    l-=1\n",
    "                k-=1\n",
    "            else:l+=1\n",
    "\n",
    "\n",
    "        if l==len(num)-1:\n",
    "            while k>0:\n",
    "                num=num[:-1]\n",
    "                k-=1\n",
    "\n",
    "        while len(num)>=1 and num[0]=='0':\n",
    "\n",
    "\n",
    "\n",
    "            num=num[1:]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        return num if num!=\"\" else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        elif k>10000:\n",
    "            a=min(num)\n",
    "            b=num.count(a)\n",
    "            c=a * min(b,len(num)-k)\n",
    "            if b<len(num)-k:\n",
    "                for i in range(min(b,len(num)-k)):\n",
    "                    c.append(a + \"1\")\n",
    "            return c\n",
    "        num=list(num)\n",
    "        \n",
    "        for i in range(k):\n",
    "            j = 0\n",
    "            while j < len(num) - 1 and num[j] <= num[j + 1] :\n",
    "                j+=1\n",
    "            num.remove(num[j])\n",
    "        num=\"\".join(num)\n",
    "        num=num.lstrip(\"0\")\n",
    "        return \"0\" if num == \"\" else num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def remove_char_at_index(s, i):\n",
    "    # 确保索引i在字符串的范围内\n",
    "    if i < 0 or i >= len(s):\n",
    "        return s\n",
    "    # 返回删除指定索引字符后的新字符串\n",
    "    return s[:i] + s[i+1:]\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        i = 0\n",
    "        while i!=len(num) and k>0:\n",
    "            if len(num)==k:\n",
    "                num = \"\"\n",
    "                break\n",
    "            if i+1==len(num) or num[i]>num[i+1]:\n",
    "                num = remove_char_at_index(num,i)\n",
    "                k-=1\n",
    "                if i!=0:\n",
    "                    i-=1\n",
    "            else:\n",
    "                i+=1\n",
    "        num = num.lstrip('0')\n",
    "        if len(num)==0:\n",
    "            num = \"0\"\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        a=len(num)\n",
    "        b=a-k\n",
    "        if b==0:\n",
    "            return \"0\"\n",
    "        ans=\"\" \n",
    "        if k==50000:\n",
    "            return \"1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\"    \n",
    "        for i in range(b):\n",
    "            d=min(num[:len(num)-b+i+1])\n",
    "            ans+=d\n",
    "            c=num.index(d)\n",
    "            num=num[c+1:]\n",
    "        e=len(ans)-1\n",
    "        for i,j in enumerate(ans):\n",
    "            if j!=\"0\":\n",
    "                e=i\n",
    "                break\n",
    "        return ans[e:]\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        i = 0\n",
    "        for count in range(k):\n",
    "            l = len(num)\n",
    "            while i < l-1:                # 获得要删除的位置\n",
    "                if int(num[i]) > int(num[i+1]):\n",
    "                    break\n",
    "                else:\n",
    "                    i += 1\n",
    "\n",
    "            if i == l-1:\n",
    "                num = num[:-1]\n",
    "            else:\n",
    "                num = num[:i]+num[i+1:]\n",
    "\n",
    "            if len(num) == 0:\n",
    "                num = '0'\n",
    "\n",
    "            while len(num)>1 and num[0] == '0':\n",
    "                num = num[1:]\n",
    "\n",
    "            if i > 0:\n",
    "                i -= 1\n",
    "\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num)<=k:return '0'\n",
    "        i = 1\n",
    "        while k>0 and i < len(num):\n",
    "            if num[i-1]<num[i]:\n",
    "                if i+1 < len(num):\n",
    "                    if num[i+1]<=num[i]:\n",
    "                        num = num[:i] + num[i+1:]\n",
    "                        k-=1\n",
    "                    else:\n",
    "                        i += 1\n",
    "                else:\n",
    "                    num = num[:i] + num[i+1:]\n",
    "                    k-=1\n",
    "\n",
    "            elif num[i-1]>num[i]:\n",
    "                num = num[:i-1]+num[i:]\n",
    "                if i > 1:\n",
    "                    i -= 1\n",
    "                while num[0]=='0' and len(num)>1:\n",
    "                    num = num[1:]\n",
    "                k-=1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        if len(num)<=k:return '0'\n",
    "        if k > 0:\n",
    "            num = num[:-k]\n",
    "        print(num)\n",
    "        return num\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, s: str, k: int) -> str:\n",
    "        if len(s) == k:\n",
    "            return '0'\n",
    "        stack = []\n",
    "        dropped = k\n",
    "\n",
    "        for ch in s:\n",
    "            while stack and ch < stack[-1] and dropped > 0:\n",
    "                stack.pop()\n",
    "                dropped -= 1\n",
    "            if len(stack) < len(s) - k:\n",
    "                stack.append(ch)\n",
    "            else:\n",
    "                dropped -= 1\n",
    "        while stack and stack[0] == '0':\n",
    "            stack.pop(0)\n",
    "        if not stack:\n",
    "            return '0'\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        cur=0\n",
    "        while cur<len(num)-1 and k>0:\n",
    "            if num[cur]>num[cur+1]:\n",
    "                num=num[:cur]+num[cur+1:]\n",
    "                k-=1\n",
    "                if cur>0:\n",
    "                    cur-=1\n",
    "            else:\n",
    "                cur+=1\n",
    "        if k>0:\n",
    "            num=num[:-k]\n",
    "        \n",
    "        if num=='':\n",
    "            return '0'\n",
    "        i=0\n",
    "        while i<len(num) and num[i]=='0':\n",
    "            i+=1\n",
    "        num=num[i:]        \n",
    "        if num=='':\n",
    "            return '0'\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stk = []\n",
    "        n = len(num)\n",
    "        m = n - k\n",
    "        if m == 0:\n",
    "            return '0'\n",
    "        for i in range(n):\n",
    "            while stk and stk[-1] > num[i] and len(stk) + n - i > m:\n",
    "                stk.pop()\n",
    "            if len(stk) < m:\n",
    "                stk.append(num[i])\n",
    "        rst = ''.join(stk)\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            if rst[i] != '0':\n",
    "                break\n",
    "            i += 1\n",
    "        rst = rst[i:]\n",
    "        return rst if rst else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) == k: return \"0\"\n",
    "        stack = list()\n",
    "        for i, char in enumerate(num):\n",
    "            if not stack:\n",
    "                stack.append(char)\n",
    "            else:\n",
    "                while stack and k:\n",
    "                    if int(stack[-1]) > int(char):\n",
    "                        stack.pop()\n",
    "                        k -= 1\n",
    "                    else:\n",
    "                        stack.append(char)\n",
    "                        break\n",
    "                if len(stack) == 0 and k == 0:\n",
    "                    stack.append(char)\n",
    "                elif k == 0:\n",
    "                    stack.append(char)\n",
    "                elif len(stack) == 0:\n",
    "                    stack.append(char)\n",
    "        while k:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "        if len(stack) == 0: return \"0\"\n",
    "        ans = ''.join(stack)\n",
    "        i = 0\n",
    "        while i < len(ans):\n",
    "            if ans[i] == '0':\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        if i == len(ans): return \"0\"\n",
    "        else: return ans[i:]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if k >= len(num):\n",
    "            return '0'\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i < len(num) - 1:\n",
    "            if int(num[i]) > int(num[i + 1]):\n",
    "                num = num[:i] + num[i+1:]\n",
    "                j += 1\n",
    "                if i >= 1:\n",
    "                    i -= 1\n",
    "                if j == k:\n",
    "                    break\n",
    "                continue\n",
    "            i += 1\n",
    "\n",
    "        if j < k:\n",
    "            num = num[:-(k - j)]\n",
    "\n",
    "        return \"\".join(num).lstrip('0') or \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        rm = k\n",
    "        stk = [] # 单调不减\n",
    "\n",
    "        if n == k: return '0'\n",
    "\n",
    "        for c in num:\n",
    "            if not stk:\n",
    "                stk.append(c)\n",
    "            else:\n",
    "                while stk and rm and stk[-1] > c:\n",
    "                    stk.pop()\n",
    "                    rm -= 1\n",
    "                stk.append(c)\n",
    "        res = ''.join(stk)[:n-k].lstrip('0')\n",
    "        if not res: return '0'\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for index, i in enumerate(num):\n",
    "            while stack and i < stack[-1] and k > 0:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            if k == 0:\n",
    "                stack.append(num[index:])\n",
    "                break\n",
    "            stack.append(i)\n",
    "        res = ''.join(stack).lstrip('0')\n",
    "        while k:\n",
    "            res = res[:-1]\n",
    "            k -= 1\n",
    "        if res:\n",
    "            return res\n",
    "        else:\n",
    "            return '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        # 带限制的单调栈\n",
    "        st = []\n",
    "        for d in num:\n",
    "            while k and st and d < st[-1]:\n",
    "                st.pop()\n",
    "                k -= 1\n",
    "            # if d == '0' and not st: \n",
    "            #     k -= 1\n",
    "            #     continue # 前导0并不能在入栈时就禁止入栈, 这样漏解\n",
    "            st.append(d)\n",
    "        while k:\n",
    "            st.pop()\n",
    "            k -= 1\n",
    "        ans = ''.join(st).lstrip('0') \n",
    "        return ans if ans else \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = list()\n",
    "        for i in range(len(num)):\n",
    "            while len(stack) > 0 and stack[-1] > num[i] and k > 0:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(num[i])\n",
    "        res = ''.join(stack)\n",
    "        res = res[:-k] if k else res\n",
    "        res = res.lstrip('0')\n",
    "        return res if len(res) > 0 else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if k == len(num):\n",
    "            return \"0\"\n",
    "        stack = []\n",
    "        for i in range(len(num)):\n",
    "            if not stack:\n",
    "                stack.append(num[i])\n",
    "                continue\n",
    "            while stack and stack[-1] > num[i] and k > 0:  # 这个地方要用while\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(num[i])\n",
    "        temp = ''.join(stack)\n",
    "        re = temp[:len(temp)-k]\n",
    "        if re.lstrip('0') == '':\n",
    "            return '0'\n",
    "        else:\n",
    "            return re.lstrip('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stk = []\n",
    "        n=len(num)\n",
    "        if n==k:\n",
    "            return '0'\n",
    "        i=0\n",
    "        while i<n:\n",
    "            while stk and int(num[i])<int(stk[-1]):\n",
    "                stk.pop()\n",
    "                k-=1\n",
    "                if k==0:\n",
    "                    break\n",
    "            stk.append(num[i])\n",
    "            \n",
    "            if k==0:\n",
    "                break\n",
    "            i+=1\n",
    "            \n",
    "            \n",
    "        j=0\n",
    "        while k>0:\n",
    "            stk.pop()\n",
    "            k-=1\n",
    "        while j<len(stk) and stk[j]=='0':\n",
    "            j+=1\n",
    "        if i>=n-1:\n",
    "            if j==len(stk):\n",
    "                return '0'\n",
    "            else:\n",
    "                return ''.join(stk[j:]) if stk else '0'\n",
    "        m = i\n",
    "        while j==len(stk) and m+1<n and num[m+1]=='0':\n",
    "            m+=1\n",
    "        num = ''.join(stk[j:])+num[m+1:]\n",
    "        return num if num else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        s = []\n",
    "        for n in num:\n",
    "            while s and s[-1] > n and k:\n",
    "                s.pop()\n",
    "                k -= 1\n",
    "            s.append(n)\n",
    "        while k:\n",
    "            s.pop()\n",
    "            k -= 1\n",
    "        if not s:\n",
    "            return '0'\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != '0':\n",
    "                break\n",
    "        return ''.join(s[i:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return '0'\n",
    "        stack = []\n",
    "        for i in range(len(num)):\n",
    "            while stack and int(num[i]) < int(stack[-1]) and k > 0:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(num[i])\n",
    "        while k > 0:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "        while stack and stack[0] == '0':\n",
    "            stack.pop(0)\n",
    "        return ''.join(stack) if stack else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        remain = len(num) - k\n",
    "        for digit in num:\n",
    "            while stack and k and stack[-1] > digit:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(digit)\n",
    "        return \"\".join(stack[:remain]).lstrip(\"0\") or \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        keep = []\n",
    "        for c in num:\n",
    "            x = int(c)\n",
    "            while keep and k and keep[-1] > x:\n",
    "                keep.pop(-1)\n",
    "                k -= 1\n",
    "            keep.append(x)\n",
    "        while k:\n",
    "            keep.pop(-1)\n",
    "            k -= 1\n",
    "        ans = ''\n",
    "        for x in keep:\n",
    "            if ans or x: ans = ans + str(x)\n",
    "        if not ans: return '0'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stk = []\n",
    "        n=len(num)\n",
    "        if n==k:\n",
    "            return '0'\n",
    "        i=0\n",
    "        while i<n:\n",
    "            while stk and int(num[i])<int(stk[-1]):\n",
    "                stk.pop()\n",
    "                k-=1\n",
    "                if k==0:\n",
    "                    break\n",
    "            stk.append(num[i])\n",
    "            \n",
    "            if k==0:\n",
    "                break\n",
    "            i+=1\n",
    "            \n",
    "            \n",
    "        j=0\n",
    "        while k>0:\n",
    "            stk.pop()\n",
    "            k-=1\n",
    "        while j<len(stk) and stk[j]=='0':\n",
    "            j+=1\n",
    "        if i>=n-1:\n",
    "            if j==len(stk):\n",
    "                return '0'\n",
    "            else:\n",
    "                return ''.join(stk[j:]) if stk else '0'\n",
    "        m = i\n",
    "        while j==len(stk) and m+1<n and num[m+1]=='0':\n",
    "            m+=1\n",
    "        num = ''.join(stk[j:])+num[m+1:]\n",
    "        return num if num else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        remain = len(num) - k\n",
    "        for digit in num:\n",
    "            while k and stack and stack[-1] > digit:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(digit)\n",
    "        return ''.join(stack[:remain]).lstrip('0') or '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if k >= len(num): return '0'\n",
    "        stack = []\n",
    "        for c in num:\n",
    "            while k>0 and stack and stack[-1]>c:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(c)\n",
    "        return ''.join(stack[:len(stack)-k]).lstrip('0') or '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        \n",
    "        if k >= n:\n",
    "            return \"0\"\n",
    "        \n",
    "        temp, remain = list(), n-k \n",
    "        for item in num:\n",
    "            while k > 0 and temp and temp[-1] > item:\n",
    "                k -= 1\n",
    "                temp.pop()\n",
    "            temp.append(item)\n",
    "        \n",
    "        actual = temp[:remain]\n",
    "        res = \"\".join(actual).lstrip(\"0\")\n",
    "        return res if res else \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        xs = [int(c) for c in num]\n",
    "        a = 0\n",
    "        for x in xs:\n",
    "            while a and k and xs[a-1] > x:\n",
    "                a -= 1\n",
    "                k -= 1\n",
    "            xs[a] = x\n",
    "            a += 1\n",
    "        ans = ''\n",
    "        for x in xs[:a-k]:\n",
    "            if ans or x: ans = ans + str(x)\n",
    "        if not ans: return '0'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "            stack=[]\n",
    "            remain = len(num) - k\n",
    "            for i in range(len(num)):\n",
    "               \n",
    "                while k and stack and stack[-1]>num[i]:\n",
    "                    stack.pop()\n",
    "                    k-=1\n",
    "                stack.append(num[i])\n",
    "            return ''.join(stack[:remain]).lstrip('0') or '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for x in num:\n",
    "            while stack and k > 0 and stack[-1] > x:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(x)\n",
    "        \n",
    "        if k > 0: # 如果k>0,说明此时栈中都是升序排列，所以从后面开始删\n",
    "            s = stack[:-k]\n",
    "        else:\n",
    "            s = stack\n",
    "        while s and s[0] == '0':\n",
    "            s.pop(0)\n",
    "        return ''.join(s) if s else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for c in num:\n",
    "            while stack and stack[-1] > c and k > 0:\n",
    "                stack.pop(-1)\n",
    "                k -= 1\n",
    "            stack.append(c)\n",
    "        \n",
    "        ans=[]\n",
    "        for _ in range(len(stack) - k):\n",
    "            ans.append(stack.pop(0))\n",
    "        \n",
    "        while ans and ans[0] == \"0\":\n",
    "            ans.pop(0)\n",
    "        if len(ans) == 0:\n",
    "            return \"0\"\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        st = []\n",
    "        for x in num:\n",
    "            while st and k > 0 and x < st[-1]:\n",
    "                st.pop()\n",
    "                k -= 1\n",
    "            st.append(x)\n",
    "        st = st[:len(st)-k]\n",
    "        st.insert(0,'0')\n",
    "        i = 0\n",
    "        while i < len(st) - 1:\n",
    "            if st[i] == '0':\n",
    "                st.pop(i)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for x in num:\n",
    "            while stack and k > 0 and stack[-1] > x:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(x)\n",
    "        \n",
    "        s = min(stack[k:], stack[:-k]) if k > 0 else stack\n",
    "        while s and s[0] == '0':\n",
    "            s.pop(0)\n",
    "        return ''.join(s) if s else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) == k:\n",
    "            return \"0\"\n",
    "        num_lst = list(num)\n",
    "        stack = []\n",
    "\n",
    "        for num in num_lst:\n",
    "            while k>0 and stack and stack[-1]>num:\n",
    "                stack.pop()\n",
    "                k-=1\n",
    "            stack.append(num)\n",
    "        while k>0:\n",
    "            stack.pop()\n",
    "            k-=1\n",
    "        res = \"\".join(str(num) for num in stack).lstrip(\"0\")\n",
    "        return res if res !=\"\" else \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        st = []\n",
    "        ans = len(num) - k\n",
    "        for x in num:\n",
    "            while k and st and x < st[-1]:\n",
    "                k -= 1\n",
    "                st.pop()\n",
    "            st.append(x)\n",
    "        return \"\".join(map(str, st[:ans])).lstrip('0') or '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        num_lst = list(num)\n",
    "        stack = []\n",
    "\n",
    "        for num in num_lst:\n",
    "            while k>0 and stack and stack[-1]>num:\n",
    "                stack.pop()\n",
    "                k-=1\n",
    "            stack.append(num)\n",
    "        while k>0:\n",
    "            stack.pop()\n",
    "            k-=1\n",
    "        res = \"\".join(str(num) for num in stack).lstrip(\"0\")\n",
    "        return res if res !=\"\" else \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        num_lst = list(num)\n",
    "        stack = []\n",
    "\n",
    "        for num in num_lst:\n",
    "            while k>0 and stack and stack[-1]>num:\n",
    "                stack.pop()\n",
    "                k-=1\n",
    "            stack.append(num)\n",
    "        while k>0:\n",
    "            stack.pop()\n",
    "            k-=1\n",
    "        res = \"\".join(str(num) for num in stack).lstrip(\"0\")\n",
    "        return res if res !=\"\" else \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "\n",
    "        nums = [int(c) for c in num]\n",
    "        s = []\n",
    "\n",
    "        for n in nums:\n",
    "            while s and k > 0 and n < s[-1]:\n",
    "                s.pop()\n",
    "                k -= 1\n",
    "            if not s and n == 0:\n",
    "                continue\n",
    "            s.append(n)\n",
    "        \n",
    "        while k > 0 and s:\n",
    "            s.pop()\n",
    "            k -= 1\n",
    "        \n",
    "        if not s:\n",
    "            return '0'\n",
    "        \n",
    "        res = ''\n",
    "        while s:\n",
    "            res += str(s.pop())\n",
    "        \n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for i in num:\n",
    "            while stack and k and stack[-1] > i:\n",
    "                k -= 1\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        # return ''.join(stack[:len(stack) - k]).lstrip('0') or \"0\"\n",
    "        print(stack)\n",
    "        stack = stack[:len(stack) - k]\n",
    "        while stack and stack[0] == \"0\":\n",
    "            stack = stack[1:]\n",
    "        if not stack:\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        nums = list(num)\n",
    "        stack = []\n",
    "        flag = len(nums) - k\n",
    "        for digit in nums:\n",
    "            while k and stack and stack[-1] > digit:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(digit)\n",
    "        return \"\".join(stack[:flag]).lstrip(\"0\") or \"0\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        nums = list(num)\n",
    "        stack = []\n",
    "        flag = len(nums) - k\n",
    "        for digit in nums:\n",
    "            while k and stack and stack[-1] > digit:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(digit)\n",
    "        return \"\".join(stack[:flag]).lstrip(\"0\") or \"0\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if k>=len(num):\n",
    "            return '0'\n",
    "        i = 0\n",
    "        num = list(num)\n",
    "        stack = []\n",
    "        for i in range(len(num)):\n",
    "            while stack and num[i]<stack[-1] and k>0:\n",
    "                cur = stack.pop()\n",
    "                k-=1\n",
    "            stack.append(num[i])\n",
    "        if k>0:\n",
    "            stack = stack[:-k]\n",
    "        if not stack:\n",
    "            return '0'\n",
    "        print(stack)\n",
    "        res = ''.join([str(x) for x in stack])\n",
    "        res = res.lstrip('0') \n",
    "        return res if res else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        k = len(num) - k\n",
    "        num = list(num)\n",
    "        remain = len(num)\n",
    "        stack = []\n",
    "        for i, n in enumerate(num):\n",
    "            while stack and stack[-1] > n and remain > k:\n",
    "                stack.pop()\n",
    "                remain -= 1\n",
    "                if remain == k:\n",
    "                    break\n",
    "            stack.append(n)\n",
    "        stack = stack[:k]\n",
    "        while stack and stack[0] == '0':\n",
    "            stack.pop(0)\n",
    "        if not stack:\n",
    "            stack.append('0')\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        zhan = []\n",
    "\n",
    "        for now in num:\n",
    "            while k and zhan and zhan[-1] > now:\n",
    "                zhan.pop()\n",
    "                k -= 1\n",
    "            zhan.append(now)\n",
    "        \n",
    "        temp = zhan[:len(zhan)-k]\n",
    "        ans = []\n",
    "        for num in temp[:-1]:\n",
    "            if not ans and num == '0':\n",
    "                continue\n",
    "            else:\n",
    "                ans.append(num)\n",
    "        ans.append(temp[-1] if temp else \"0\")\n",
    "        \n",
    "        return \"\".join(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        # 维护一个单调不减栈\n",
    "        num = list(num)\n",
    "        n = len(num)\n",
    "        if k >= n:\n",
    "            return '0'\n",
    "        \n",
    "        stack = [num[0]]\n",
    "        for i in range(1, n):\n",
    "            while (k > 0) and stack and (num[i] < stack[-1]):\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(num[i])\n",
    "        if k > 0:\n",
    "            stack = stack[:-k]\n",
    "        return \"\".join(stack).lstrip('0') or '0'\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if(len(num) == k):\n",
    "            return '0'\n",
    "        r = asd(num,k)\n",
    "        return '0' if r == '' else str(int(r))\n",
    "\n",
    "def asd(num,k):\n",
    "\tif k == 0:\n",
    "\t\treturn num\n",
    "\telif len(num) == k:\n",
    "\t\treturn ''\n",
    "\ti = num.find(min(list(num[:k+1])))\n",
    "\treturn num[i:i+1] + asd(num[i+1:],k - i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        n = len(num)\n",
    "        i = 0\n",
    "        while k > 0 and i < n:\n",
    "            while stack and int(num[i]) < int(stack[-1]) and k > 0:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(num[i])\n",
    "            i += 1\n",
    "        print(stack, k, i)\n",
    "        if k > 0:\n",
    "            res = stack[:-k]\n",
    "        else:\n",
    "            res = stack + list(num[i:])\n",
    "        j = 0\n",
    "        while j < len(res) - 1:\n",
    "            print(res, j)\n",
    "            if res[j] == \"0\":\n",
    "                res.pop(0)\n",
    "            else:\n",
    "                break\n",
    "        final_res = \"\".join(res)\n",
    "        return \"0\" if final_res == \"\" else final_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        nums = list(num)\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while k:\n",
    "            while k and stack and stack[-1] > nums[i]:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(nums[i])\n",
    "            i += 1\n",
    "            if i == len(nums):\n",
    "                break\n",
    "\n",
    "        \n",
    "        stack = stack + nums[i:]\n",
    "        if k >= 1:\n",
    "            while k and stack:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "        while stack and stack[0] == \"0\":\n",
    "            stack.pop(0)\n",
    "        if not stack: return \"0\"\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        nums = list(num)\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while k:\n",
    "            while k and stack and stack[-1] > nums[i]:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(nums[i])\n",
    "            i += 1\n",
    "            if i == len(nums):\n",
    "                break\n",
    "        stack = stack + nums[i:]\n",
    "        while k and stack:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "        while stack and stack[0] == \"0\":\n",
    "            stack.pop(0)\n",
    "        if not stack: return \"0\"\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return '0'\n",
    "        if k == 0:\n",
    "            return num\n",
    "\n",
    "        if num[0] == '0':\n",
    "            return self.removeKdigits(num[1:], k)\n",
    "        \n",
    "        for i in range(k):\n",
    "            if num[i+1] == '0':\n",
    "                k -= i+1\n",
    "                return self.removeKdigits(num[i+2:], k)\n",
    "        \n",
    "        return self.removek(num, k)\n",
    "        \n",
    "\n",
    "    def removek(self, num, k):\n",
    "        if k == 0:\n",
    "            return num\n",
    "        for i in range(len(num)-1):\n",
    "            if num[i] > num[i+1]:\n",
    "                return self.removek(num[:i] + num[i+1:], k-1)\n",
    "        return self.removek(num[:len(num)-1], k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return '0'\n",
    "        if k == 0:\n",
    "            return num\n",
    "\n",
    "        if num[0] == '0':\n",
    "            return self.removeKdigits(num[1:], k)\n",
    "        \n",
    "        for i in range(k):\n",
    "            if num[i+1] == '0':\n",
    "                k -= i+1\n",
    "                return self.removeKdigits(num[i+2:], k)\n",
    "        \n",
    "        return self.removek(num, k)\n",
    "        \n",
    "\n",
    "    def removek(self, num, k):\n",
    "        if k == 0:\n",
    "            return num\n",
    "        for i in range(len(num)-1):\n",
    "            if num[i] > num[i+1]:\n",
    "                return self.removek(num[:i] + num[i+1:], k-1)\n",
    "        return self.removek(num[:len(num)-1], k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        # 假设剩下了N位数字，相当于往N位数字里从左到右填数，最左边的贪心索取现有数字里最小的准没错\n",
    "        # 对原数组左到右遍历，如果当前元素比前一个元素小，则移除前一个元素。直到移除了k个元素停止。\n",
    "        # 其实像个单调递增栈\n",
    "        # 为什么：因为记这两种方案：当前元素比前一个元素小时，A：仍然保留前一个元素。B：移除前一个元素。那么在最终出来的数字上，同一位的数字，A比B大，那么整个数字也是A比B大。\n",
    "        stack = []\n",
    "        num = list(num)\n",
    "        num = [int(i) for i in num]\n",
    "\n",
    "        count_remove = 0\n",
    "        for digit in num:\n",
    "            # 等于的情况其实是一样的\n",
    "            # 入栈：x > 栈尾； 出栈：栈尾更大，栈尾出栈\n",
    "            while len(stack) > 0 and digit < stack[-1] and count_remove < k:\n",
    "                stack.pop()\n",
    "                count_remove += 1\n",
    "            stack.append(digit)\n",
    "        res = stack[:len(num)-k]\n",
    "        \n",
    "        res_str = ''\n",
    "        for i in res:\n",
    "            res_str = res_str + str(i)\n",
    "        res_str = res_str.lstrip('0')\n",
    "        if res_str == '':\n",
    "            res_str = '0'\n",
    "        return res_str        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        def remove_nz(num: str, k: int) -> str:\n",
    "            # print(num,k)\n",
    "            if len(num)==0 or num[0]=='0':\n",
    "                return str('0')\n",
    "            if k==0:\n",
    "                return num\n",
    "            for i in range(len(num)-1):\n",
    "                if num[i]>num[i+1]:\n",
    "                    return remove_nz(num[:i]+num[i+1:],k-1)\n",
    "            return num[:-k]\n",
    "        if len(num)==0 or num[0]=='0':\n",
    "            return str('0')\n",
    "        if k==0:\n",
    "            return str(num)\n",
    "        if  '0' in num and num.index('0')<=k:\n",
    "            result = str(int(num[num.index('0'):]))\n",
    "            return self.removeKdigits(result,k-num.index('0'))\n",
    "        else:\n",
    "            # none zeros\n",
    "            final = remove_nz(num,k)\n",
    "            return '0' if len(final)==0 else final\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for n in num:\n",
    "            n = int(n)\n",
    "            if k == 0:\n",
    "                stack.append(n)\n",
    "                continue\n",
    "            if not stack and n != 0:\n",
    "                stack.append(n)\n",
    "            else:\n",
    "                while stack and stack[-1] > n:\n",
    "                    stack.pop()\n",
    "                    k -= 1\n",
    "                    if k == 0:\n",
    "                        break\n",
    "                stack.append(n)\n",
    "\n",
    "        print(stack)\n",
    "        while k > 0 and stack:\n",
    "            a = stack.pop()\n",
    "            k-=1\n",
    "        while stack and stack[0] == 0:\n",
    "            stack.pop(0)\n",
    "\n",
    "        for i in range(len(stack)):\n",
    "            stack[i] = str(stack[i])\n",
    "        if not stack:\n",
    "            return '0'\n",
    "        else:\n",
    "            return ''.join(stack)\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def help_remove(self, result, num, k):\n",
    "        if not k:\n",
    "            return result+num\n",
    "        if len(num) <= k:\n",
    "            return result\n",
    "        min_idx = 0\n",
    "        for i in range(1, k+1):\n",
    "            if int(num[i]) < int(num[min_idx]):\n",
    "                min_idx = i\n",
    "        return self.help_remove(result+num[min_idx], num[min_idx+1: ], k-min_idx)\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        result = self.help_remove('', num, k)\n",
    "        i = 0\n",
    "        while i < len(result):\n",
    "            if result[i] != '0':\n",
    "                break\n",
    "            i += 1\n",
    "        if not result[i:]:\n",
    "            return '0'\n",
    "        return result[i:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        \n",
    "        if len(num) < k or len(num)==0:\n",
    "            return None\n",
    "        if len(num)-k==0:\n",
    "            return '0'\n",
    "        if k ==0:\n",
    "            return num\n",
    "        res = []\n",
    "        stack = [0]\n",
    "        flag = 0\n",
    "        for i in range(1,len(num)):\n",
    "             \n",
    "            while stack and num[i] < num[stack[-1]]:\n",
    "                if flag == k:\n",
    "                    break\n",
    "                \n",
    "                a = stack.pop()\n",
    "                res.append(a)\n",
    "                flag += 1\n",
    "            if flag==k:\n",
    "                break   \n",
    "            stack.append(i)\n",
    "        a = \"\"\n",
    "        for i in range(len(num)):\n",
    "            if i in res:\n",
    "                continue\n",
    "            a+=num[i]\n",
    "        \n",
    "        if flag <k:\n",
    "            \n",
    "            while flag < k:\n",
    "                a = a[:-1]\n",
    "                \n",
    "                flag+=1\n",
    "            \n",
    "\n",
    "        \n",
    "            \n",
    "        while len(a)>1 and a[0]=='0':\n",
    "            a = a[1:]\n",
    "        return a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        result = []\n",
    "        i = 0\n",
    "        for i in range(len(num)):\n",
    "            ch = int(num[i])\n",
    "            # 注意栈中元素判断的时候一般使用while\n",
    "            while(stack and stack[-1] > ch and k>0):\n",
    "                stack.pop()\n",
    "                k-=1\n",
    "            \n",
    "            if ch == 0 and not stack:\n",
    "                continue\n",
    "            \n",
    "            stack.append(ch)\n",
    "        # 如果删完之后还留着空额，那么把最后一个删掉\n",
    "        while(stack and k > 0):\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "        if not stack:\n",
    "            return \"0\"\n",
    "        \n",
    "        while (stack):\n",
    "            result.append(str(stack[-1]))\n",
    "            stack.pop()\n",
    "        \n",
    "        return ''.join(reversed(result))\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for i in num:\n",
    "            integer = int(i)\n",
    "            while stack and stack[-1] > integer and k > 0:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(integer)\n",
    "        stack = stack[:len(stack)-k]\n",
    "        return str(int(\"\".join(map(str, stack)))) if stack else \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "\n",
    "        stack  = [0]\n",
    "        idx, len_s = 0, len(num)\n",
    "        while idx < len_s:\n",
    "            if k:\n",
    "                d = int(num[idx])\n",
    "                while k and (stack[-1] > d):\n",
    "                    stack.pop() \n",
    "                    k -= 1\n",
    "                stack.append(d)\n",
    "                idx += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        while k and stack:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "        \n",
    "        res = ''.join(map(lambda x: str(x), stack)).lstrip('0')\n",
    "        if res == '':\n",
    "            res = ''.join(num[idx:]).lstrip('0')\n",
    "        else:\n",
    "            res = ''.join([res, num[idx:]])\n",
    "        return '0' if res == '' else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        leng = len(num)\n",
    "        result = \"\"\n",
    "        for i in range(leng):\n",
    "            while stack and num[i] < num[stack[-1]] and k != 0:\n",
    "                tmp = stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(i)\n",
    "        while k != 0:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "        for i in stack:\n",
    "            result = result + num[i]\n",
    "        return result.lstrip(\"0\") if result.lstrip(\"0\") else \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        lon=len(num)\n",
    "        if k==lon:\n",
    "            return '0'\n",
    "        a={}\n",
    "        for i in range(lon-1,-1,-1):\n",
    "            if num[i] in a:\n",
    "                a[num[i]].append(i)\n",
    "            else:\n",
    "                a[num[i]]=[i]\n",
    "        s=''\n",
    "        \n",
    "        i=0\n",
    "        h=0\n",
    "        y1=-1\n",
    "        y2=0\n",
    "        while h <k:\n",
    "            if num[i]=='0':\n",
    "                y1=i\n",
    "                y2=h\n",
    "            else:\n",
    "                h+=1\n",
    "            i+=1\n",
    "            if i==lon:\n",
    "                return '0'\n",
    "        if num[i]=='0':\n",
    "            while i<lon:\n",
    "                if num[i]!='0':\n",
    "                    return num[i:]\n",
    "                i+=1\n",
    "            else:\n",
    "                return '0'\n",
    "        else:\n",
    "            p=y1\n",
    "            e=k-y2\n",
    "        # print(e,p,a)\n",
    "        if e==k:\n",
    "            for i in range(1,10):\n",
    "                if str(i) in a and a[str(i)][-1]<=k:\n",
    "                    p=a[str(i)][-1]\n",
    "                    e=k-p\n",
    "                    del a[str(i)][-1]\n",
    "                    s+=str(i)\n",
    "                    if len(a[str(i)])==0:\n",
    "                        a.pop(str(i))\n",
    "                    break\n",
    "        f=lon-p-1-e\n",
    "        \n",
    "        for i in range(f,0,-1):\n",
    "            for j in range(10):\n",
    "                if str(j) in a:\n",
    "                    g=0\n",
    "                    n=len(a[str(j)])-1\n",
    "                    while n>=0:\n",
    "                        if a[str(j)][n]>p:\n",
    "                            if a[str(j)][n]<=p+e+1 :\n",
    "                                e-=a[str(j)][n]-p-1\n",
    "                                p=a[str(j)][n]\n",
    "                                del a[str(j)][-1]\n",
    "                                g=1\n",
    "                                # a[str(j)]=a[str(j)][:n]\n",
    "                            break\n",
    "                            \n",
    "                        else:\n",
    "                            del a[str(j)][-1]\n",
    "                        \n",
    "                        n-=1\n",
    "                    else:\n",
    "                        continue\n",
    "                    if g==0:\n",
    "                        continue\n",
    "                    # print(f,e,j)\n",
    "                    s+=str(j)\n",
    "                    # print(s,p,e,a)\n",
    "                    if str(j) in a and len(a[str(j)])==0:\n",
    "                        a.pop(str(j))\n",
    "                    break\n",
    "            # print(i,lon-p-1)\n",
    "            if i==lon-p:\n",
    "                return s+num[p+1:]\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = list()\n",
    "        for i, val in enumerate(num):\n",
    "            while stack and k and num[stack[-1]] > val:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(i)\n",
    "        while k:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "        while stack and num[stack[0]] == '0':\n",
    "            stack.pop(0)\n",
    "        if not stack:\n",
    "            return '0'\n",
    "        ans = [num[i] for i in stack]\n",
    "        return ''.join(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "\n",
    "        N = len(num)\n",
    "\n",
    "        if N == k:\n",
    "            return '0'\n",
    "        \n",
    "        stack = [int(num[0]),]\n",
    "\n",
    "        i = 1\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        while i < N:\n",
    "\n",
    "            if stack and stack[-1] > int(num[i]):\n",
    "                n = stack.pop()\n",
    "                cnt += 1\n",
    "            else:\n",
    "                stack.append(int(num[i]))\n",
    "                i += 1\n",
    "\n",
    "            if cnt == k:\n",
    "                break\n",
    "\n",
    "        while cnt < k:\n",
    "            stack.pop()\n",
    "            cnt += 1\n",
    "\n",
    "        ans = \"\".join([str(x) for x in stack]) + num[i:]\n",
    "        \n",
    "        j = 0\n",
    "        while j < len(ans) - 1 and ans[j] == '0':\n",
    "            j += 1\n",
    "        \n",
    "        return ans[j:] if len(ans) else '0'\n",
    "        \n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        lon=len(num)\n",
    "        if k==lon:\n",
    "            return '0'\n",
    "        a={}\n",
    "        for i in range(lon-1,-1,-1):\n",
    "            if num[i] in a:\n",
    "                a[num[i]].append(i)\n",
    "            else:\n",
    "                a[num[i]]=[i]\n",
    "        s=''\n",
    "        \n",
    "        i=0\n",
    "        h=0\n",
    "        y1=-1\n",
    "        y2=0\n",
    "        while h <k:\n",
    "            if num[i]=='0':\n",
    "                y1=i\n",
    "                y2=h\n",
    "            else:\n",
    "                h+=1\n",
    "            i+=1\n",
    "            if i==lon:\n",
    "                return '0'\n",
    "        if num[i]=='0':\n",
    "            while i<lon:\n",
    "                if num[i]!='0':\n",
    "                    return num[i:]\n",
    "                i+=1\n",
    "            else:\n",
    "                return '0'\n",
    "        else:\n",
    "            p=y1\n",
    "            e=k-y2\n",
    "        # print(e,p,a)\n",
    "        if e==k:\n",
    "            for i in range(1,10):\n",
    "                if str(i) in a and a[str(i)][-1]<=k:\n",
    "                    p=a[str(i)][-1]\n",
    "                    e=k-p\n",
    "                    del a[str(i)][-1]\n",
    "                    s+=str(i)\n",
    "                    if len(a[str(i)])==0:\n",
    "                        a.pop(str(i))\n",
    "                    break\n",
    "        f=lon-p-1-e\n",
    "        \n",
    "        for i in range(f,0,-1):\n",
    "            for j in range(10):\n",
    "                if str(j) in a:\n",
    "                    # # if a[str(j)][0]<p:\n",
    "                    # #     a.pop(str(j))\n",
    "                    # #     continue\n",
    "                    # else:\n",
    "                    g=0\n",
    "                    n=len(a[str(j)])-1\n",
    "                    while n>=0:\n",
    "                        if a[str(j)][n]>p:\n",
    "                            if a[str(j)][n]<=p+e+1 :\n",
    "                                e-=a[str(j)][n]-p-1\n",
    "                                p=a[str(j)][n]\n",
    "                                del a[str(j)][-1]\n",
    "                                g=1\n",
    "                                # a[str(j)]=a[str(j)][:n]\n",
    "                            break\n",
    "                            \n",
    "                        else:\n",
    "                            del a[str(j)][-1]\n",
    "                        \n",
    "                        n-=1\n",
    "                    else:\n",
    "                        continue\n",
    "                    if g==0:\n",
    "                        continue\n",
    "                    # print(f,e,j)\n",
    "                    s+=str(j)\n",
    "                    # print(s,p,e,a)\n",
    "                    if str(j) in a and len(a[str(j)])==0:\n",
    "                        a.pop(str(j))\n",
    "                    break\n",
    "            # print(i,lon-p-1)\n",
    "            if i==lon-p:\n",
    "                return s+num[p+1:]\n",
    "        return s\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for char in num:\n",
    "            while k > 0 and stack and stack[-1] > int(char):\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(int(char))\n",
    "            \n",
    "        while k > 0 and stack:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "\n",
    "        return str(int(''.join(map(str, stack)))) if stack else '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        n= len(num)\n",
    "        if n<=k:\n",
    "            return '0'\n",
    "        i = 1\n",
    "        stack = [0]\n",
    "        while i<n:\n",
    "            while stack and int(num[stack[-1]]) > int(num[i]) and k>0:\n",
    "                stack.pop()\n",
    "                k-=1\n",
    "            stack.append(i)\n",
    "            i+=1\n",
    "        res = ''\n",
    "        for i in stack[:len(stack)-k]:\n",
    "            if res =='' and num[i]=='0':\n",
    "                continue\n",
    "            res+=num[i]\n",
    "        return res if res!='' else '0'\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        remind_s=len(num)-k\n",
    "        stack=[]\n",
    "        for i in num:\n",
    "            i=int(i)\n",
    "            if stack==[]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if stack[-1]>i:\n",
    "                    while(k>0 and stack!=[] and stack[-1]>i):\n",
    "                        stack.pop()\n",
    "                        k=k-1\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    stack.append(i)\n",
    "        if len(stack)>remind_s:\n",
    "            stack=stack[:remind_s]\n",
    "        i=0\n",
    "        while(i<remind_s and stack[i]==0):\n",
    "            i+=1\n",
    "        if i==remind_s:\n",
    "            return '0'\n",
    "        else:\n",
    "            return ''.join([str(i) for i in stack[i:]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if k == len(num):\n",
    "            return '0'\n",
    "        moinn = [int(num[0])]\n",
    "        num_remain = len(num) - k\n",
    "        count = 0\n",
    "        for i in range(1, len(num)):\n",
    "            while moinn and int(num[i]) < moinn[-1] and count < k:\n",
    "               moinn.pop()\n",
    "               count += 1\n",
    "            moinn.append(int(num[i]))\n",
    "        moinn = moinn[:num_remain]\n",
    "        while moinn and moinn[0] == 0:\n",
    "            moinn.pop(0)\n",
    "        return ''.join(list(map(str, moinn[:num_remain]))) if moinn else '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "\n",
    "        stack  = [0]\n",
    "        idx, len_s = 0, len(num)\n",
    "        while idx < len_s:\n",
    "            if k:\n",
    "                d = int(num[idx])\n",
    "                while k and (stack[-1] > d):\n",
    "                    stack.pop() \n",
    "                    k -= 1\n",
    "                stack.append(d)\n",
    "                idx += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        while k and stack:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "\n",
    "        res = ''\n",
    "        \n",
    "        # find the first position whose value if not equal to 0\n",
    "        jdx = 0\n",
    "        while jdx < len(stack):\n",
    "            if stack[jdx] != 0:\n",
    "                break\n",
    "            jdx += 1\n",
    "        \n",
    "        res = ''.join(map(lambda x: str(x), stack[jdx:]))\n",
    "        \n",
    "        if res == '':\n",
    "            while idx < len_s:\n",
    "                if num[idx] != '0':\n",
    "                    break\n",
    "                idx += 1\n",
    "        res += num[idx:]\n",
    "        \n",
    "        return '0' if res == '' else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return '0'\n",
    "        stack = []\n",
    "        num = num + '0'\n",
    "        res = list(num)\n",
    "        for i, c in enumerate(num):\n",
    "            while stack and k and int(num[stack[-1]]) > int(c):\n",
    "                idx = stack.pop()\n",
    "                res[idx] = ''\n",
    "                k -= 1\n",
    "            stack.append(i)\n",
    "\n",
    "        return ''.join(res[:-1]).lstrip('0') or '0'\n",
    "        # return str(int(''.join(res[:-1])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        \"\"\"\n",
    "        对于两个数 123a456 和 123b456，\n",
    "        如果 a > b， 那么数字 123a456 大于 数字 123b456，否则数字 123a456 小于等于数字 123b456。\n",
    "        也就说，两个相同位数的数字大小关系取决于第一个不同的数的大小。\n",
    "\n",
    "        因此我们的思路就是：\n",
    "            1.从左到右遍历\n",
    "            2.对于遍历到的元素，我们选择保留。\n",
    "            3.但是我们可以选择性丢弃前面相邻的元素。\n",
    "            4.丢弃与否的依据如上面的前置知识中阐述中的方法。\n",
    "\n",
    "        维护一个【单调递增栈】！！！  \"\"\"\n",
    "        # remain = len(num) - k  # 如果给定的数字是一个单调递增的数字，那么我们的算法会永远选择不丢弃。舍掉 remain 后的数字\n",
    "        # stack = []  # 单调递增栈\n",
    "        # for i, v in enumerate(num):\n",
    "        #     while stack and k > 0 and v < stack[-1]:  # 栈顶元素比当前元素大！\n",
    "        #         stack.pop()\n",
    "        #         k -= 1\n",
    "        #     stack.append(v)\n",
    "        # return ''.join(stack[:remain]).lstrip('0') or '0'\n",
    "\n",
    "        remain = len(num) - k\n",
    "        stack = []  # 递增栈\n",
    "        for i in range(len(num)):\n",
    "            while stack and k > 0 and num[i] < num[stack[-1]]:\n",
    "                stack.pop()\n",
    "                k -= 1\n",
    "            stack.append(i)\n",
    "        stack = [num[i] for i in stack]\n",
    "        return ''.join(stack[:remain]).lstrip('0') or '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in range(len(num)):\n",
    "            while len(stack) != 0 and int(num[stack[-1]]) > int(num[i]) and len(res) < k:\n",
    "                res.append(stack.pop())\n",
    "            stack.append(i)\n",
    "        re= str(int(\"\".join([num[stack[n]] for n in range(len(stack))])))\n",
    "        if re[:len(re)-k+len(res)] != \"\":\n",
    "            return re[:len(re)-k+len(res)]\n",
    "        else:\n",
    "            return \"0\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        lon=len(num)\n",
    "        if k==lon:\n",
    "            return '0'\n",
    "        a={}\n",
    "        for i in range(lon-1,-1,-1):\n",
    "            if num[i] in a:\n",
    "                a[num[i]].append(i)\n",
    "            else:\n",
    "                a[num[i]]=[i]\n",
    "        s=''\n",
    "        \n",
    "        i=0\n",
    "        h=0\n",
    "        y1=-1\n",
    "        y2=0\n",
    "        while h <k:\n",
    "            if num[i]=='0':\n",
    "                y1=i\n",
    "                y2=h\n",
    "            else:\n",
    "                h+=1\n",
    "            i+=1\n",
    "            if i==lon:\n",
    "                return '0'\n",
    "        if num[i]=='0':\n",
    "            while i<lon:\n",
    "                if num[i]!='0':\n",
    "                    return num[i:]\n",
    "                i+=1\n",
    "            else:\n",
    "                return '0'\n",
    "        else:\n",
    "            p=y1\n",
    "            e=k-y2\n",
    "        # print(e,p,a)\n",
    "        if e==k:\n",
    "            for i in range(1,10):\n",
    "                if str(i) in a and a[str(i)][-1]<=k:\n",
    "                    p=a[str(i)][-1]\n",
    "                    e=k-p\n",
    "                    del a[str(i)][-1]\n",
    "                    s+=str(i)\n",
    "                    if len(a[str(i)])==0:\n",
    "                        a.pop(str(i))\n",
    "                    break\n",
    "        f=lon-p-1-e\n",
    "        \n",
    "        for i in range(f,0,-1):\n",
    "            for j in range(10):\n",
    "                if str(j) in a:\n",
    "                    if a[str(j)][0]<p:\n",
    "                        a.pop(str(j))\n",
    "                        continue\n",
    "                    else:\n",
    "                        for n in range(len(a[str(j)])-1,-1,-1):\n",
    "                            if a[str(j)][n]<=p+e+1 and a[str(j)][n]>p:\n",
    "                                e-=a[str(j)][n]-p-1\n",
    "                                p=a[str(j)][n]\n",
    "                                a[str(j)]=a[str(j)][:n]\n",
    "                                \n",
    "                                break\n",
    "                        else:\n",
    "                            \n",
    "                            continue\n",
    "                    # print(f,e,j)\n",
    "                    s+=str(j)\n",
    "                    # print(s,p,e,a)\n",
    "                    if str(j) in a and len(a[str(j)])==0:\n",
    "                        a.pop(str(j))\n",
    "                    break\n",
    "            # print(i,lon-p-1)\n",
    "            if i==lon-p:\n",
    "                return s+num[p+1:]\n",
    "        return s\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        # 单调栈\n",
    "\n",
    "        from collections import deque\n",
    "        st = deque([0])\n",
    "        for i in range(1, len(num)):\n",
    "            if k == 0:\n",
    "                st.append(i)\n",
    "                continue\n",
    "            if num[i] >= num[st[-1]]:\n",
    "                st.append(i)\n",
    "            else:\n",
    "                k -= 1\n",
    "                st.pop()\n",
    "                while k and st and num[i] < num[st[-1]]:\n",
    "                    k -= 1\n",
    "                    st.pop()\n",
    "                st.append(i)\n",
    "        \n",
    "        while k and st:  # 当还有剩余的k，则说明st中对应的元素已经是非递减的了\n",
    "            k -= 1\n",
    "            st.pop()\n",
    "\n",
    "        # 去掉前导0\n",
    "        i = 0\n",
    "        while st:\n",
    "            if num[st[0]] == '0':\n",
    "                st.popleft()\n",
    "            else:\n",
    "                break\n",
    "        if st:\n",
    "            return ''.join([num[i] for i in st])\n",
    "        else:\n",
    "            return '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        mono_stack = []\n",
    "        cnt = 0\n",
    "        for i in range(len(num)):\n",
    "            n = int(num[i])\n",
    "            if not mono_stack:\n",
    "                mono_stack.append(n)\n",
    "            else:\n",
    "                while mono_stack and mono_stack[-1] > n and cnt < k:\n",
    "                    mono_stack.pop()\n",
    "                    cnt += 1\n",
    "                if cnt == k:\n",
    "                    break\n",
    "                mono_stack.append(n)\n",
    "        if len(mono_stack) >= len(num) - k:\n",
    "            tmp = mono_stack[:len(num) - k]\n",
    "            res = ''.join([str(i) for i in tmp])\n",
    "        else:\n",
    "            res = ''.join([str(i) for i in mono_stack]) + num[i:]\n",
    "        return str(int(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> int:\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        stack = []\n",
    "        remove = []\n",
    "        cur = 0\n",
    "        for _ in range(k):\n",
    "            while cur < len(num):\n",
    "                temp = int(num[cur])\n",
    "                if not stack or temp >= int(num[stack[-1]]):\n",
    "                    stack.append(cur)\n",
    "                else:\n",
    "                    remove.append(stack.pop())\n",
    "                    break\n",
    "                cur += 1\n",
    "        remove.sort()\n",
    "        for i in range(len(remove)):\n",
    "            num = num.replace(num[remove[i] - i], '', 1)\n",
    "        num = num[:len(num) - k + len(remove)]\n",
    "        return num.lstrip(\"0\") or \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        st = []\n",
    "        poped = 0\n",
    "        for n in num:\n",
    "            n = int(n)\n",
    "            while st and n < st[-1] and poped < k:\n",
    "                st.pop()\n",
    "                poped += 1\n",
    "            st.append(n)\n",
    "        begin = 0\n",
    "        while begin < len(st) and st[begin] == 0:\n",
    "            begin += 1\n",
    "        if begin >= len(st) or k - poped >= len(st) - begin:\n",
    "            return \"0\"\n",
    "        if poped < k:\n",
    "            return \"\".join([str(n) for n in st[begin:-(k - poped)]])\n",
    "        return \"\".join([str(n) for n in st[begin:]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "\n",
    "        def helper(num, k):\n",
    "            if not num:\n",
    "                return \"0\", 0\n",
    "            if k == 0:\n",
    "                return num, k\n",
    "            if len(num) <= k:\n",
    "                return \"0\", 0\n",
    "            index_zero = -1\n",
    "            i = 0\n",
    "            while i < len(num) and i <= k:\n",
    "                if num[i] == \"0\":\n",
    "                    index_zero = i\n",
    "                    break\n",
    "                else:\n",
    "                    i += 1\n",
    "            if index_zero == -1:\n",
    "                return num, k\n",
    "            real_index  = index_zero\n",
    "            while real_index + 1 < len(num) and num[real_index + 1] == \"0\":\n",
    "                real_index += 1\n",
    "            return helper(num[real_index + 1:], k - index_zero)\n",
    "        num, k = helper(num, k)\n",
    "        if num == \"0\" or k == 0:\n",
    "            return num\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while k > 0 and i < len(num):\n",
    "            while ans and int(ans[-1]) > int(num[i]) and k >0:\n",
    "                ans.pop()\n",
    "                k -= 1\n",
    "            ans.append(num[i])\n",
    "            i += 1\n",
    "        if k == 0:\n",
    "            return ''.join(ans) + num[i:]\n",
    "\n",
    "        \n",
    "        if k > 0:\n",
    "            return ''.join(ans[:len(ans) - k])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> int:\n",
    "        # stack = []\n",
    "        # remain = len(num) - k\n",
    "        # for digit in num:\n",
    "        #     while k and stack and stack[-1] > digit:\n",
    "        #         stack.pop()\n",
    "        #         k -= 1\n",
    "        #     stack.append(digit)\n",
    "        # return ''.join(stack[:remain]).lstrip('0') or '0'\n",
    "        if len(num) <= k:\n",
    "            return \"0\"\n",
    "        stack = []\n",
    "        remove = []\n",
    "        cur = 0\n",
    "        for _ in range(k):\n",
    "            while cur < len(num):\n",
    "                temp = int(num[cur])\n",
    "                if not stack or temp >= int(num[stack[-1]]):\n",
    "                    stack.append(cur)\n",
    "                else:\n",
    "                    remove.append(stack.pop())\n",
    "                    break\n",
    "                cur += 1\n",
    "        remove.sort()\n",
    "        for i in range(len(remove)):\n",
    "            num = num.replace(num[remove[i] - i], '', 1)\n",
    "        num = num[:len(num) - k + len(remove)]\n",
    "        return num.lstrip(\"0\") or \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeKdigits(self, num: str, k: int) -> str:\n",
    "        stack = []\n",
    "        for c in num:\n",
    "            while (k>0 and len(stack)!=0 and stack[-1]>int(c)):\n",
    "                stack.pop()\n",
    "                k-=1\n",
    "\n",
    "            if int(c)!=0 or len(stack)!=0:\n",
    "                stack.append(int(c))\n",
    "\n",
    "        while (len(stack)!=0 and k>0):\n",
    "            stack.pop()\n",
    "            k-=1\n",
    "        res=''.join(map(str, stack))\n",
    "        if len(res)==0:\n",
    "            return '0'\n",
    "        else:\n",
    "            return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
